package 动态规划;

import org.junit.Test;

/**
 * @description: 0-1背包
 * @author: shuai.chen@shuyun.com
 * @date: 2023/2/7 12:43 PM
 */
public class ZeroPackage {

    @Test
    public void test01(){
        f(0, 0);
        System.out.println(maxW);
    }

    //region 参考1

    public int maxW = Integer.MIN_VALUE; //存储背包中物品总重量的最大值

    int[] items = new int[]{1, 1, 2, 4, 12};
    int total = items.length;
    /**
     * 背包重量上限
     */
    int w = 10;

    /**
     *
     * @param i     i表示考察到哪个物品了
     * @param cw    cw表示当前已经装进去的物品的重量和
     */
    public void f(int i, int cw) {
        if (cw == w || i == total) { // cw==w表示装满了;i==total表示已经考察完所有的物品
            if (cw > maxW) maxW = cw;
            return;
        }
        f(i+1, cw);  // 不放
        if (cw + items[i] <= w) {// 已经超过可以背包承受的重量的时候，就不要再装了
            f(i+1,cw + items[i]);  // 放
        }
    }
    //endregion

    //region 自己写

    public void f02(int i, int pw){
        // 终止条件
        if (i == total || pw > w) {
            maxW = pw;
            return;
        }
        f02(i+1, pw);
        if (pw + items[i] <= w) {
            // 剪枝, 其实就是加条件
            f02(i + 1, pw + items[i]);
        }
    }

    //endregion

}
